package com.atguigui.leetcode;

/**
 * 790.多米诺和托米诺平铺
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2022/11/12 11:43
 */
public class P790DominoAndTrominoTiling {
    public static void main(String[] args) {
        Solution solution = new P790DominoAndTrominoTiling().new Solution();
        // TO TEST
    }

    class Solution {
        static final int MOD = 1000000007;

        public int numTilings(int n) {
            int[][] dp = new int[n + 1][4];
            dp[0][3] = 1;
            for (int i = 1; i <= n; i++) {
                dp[i][0] = dp[i - 1][3];
                dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
                dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
                dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;
            }
            return dp[n][3];

        }
    }
}
